226. Invert Binary Tree

tags: Easy、Tree

Given the root of a binary tree, invert the tree, and return its root.

解法:

 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL) {
        return root;
    }
    
    invertTree(root->left);
    invertTree(root->right);
    
    struct TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;

    return root;
}

257. Binary Tree Paths

tags: Easy、Tree

Given the root of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void dfs (struct TreeNode* node, char* path, int pathLen, char*** paths, int* pathsSize){
    if (node != NULL) {
        if (node->right == NULL && node->left == NULL) {
            sprintf(path + pathLen, "%d", node->val);
        }
        else {
            sprintf(path + pathLen, "%d->", node->val);
        }
        pathLen += strlen(path + pathLen);

        if (node->left == NULL && node->right == NULL) {
            (*paths)[*pathsSize] = malloc((pathLen+1) * sizeof(char));
            strcpy((*paths)[*pathsSize], path);
            (*pathsSize)++;
        }
        else {
            dfs(node->left, path, pathLen, paths, pathsSize);
            dfs(node->right, path, pathLen, paths, pathsSize);
        }
        path[pathLen] = '\0';
    }
}

char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
    char** TreePaths = (char**)malloc(100 * sizeof(char*));
    *returnSize = 0;

    char path[1024] = "";
    dfs(root, path, 0, &TreePaths, returnSize);
    return TreePaths;
}

563. Binary Tree Tilt

tags: Easy、Tree

Given the root of a binary tree, return the sum of every tree node's tilt.
The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int treeSum(struct TreeNode* t, int* count) {
    if (t == NULL) {
        return 0;
    }
    int leftNum = treeSum(t->left, count);
    int rightNum = treeSum(t->right, count);

    *count += abs(leftNum - rightNum);
    return (leftNum + rightNum + t->val);
}

int findTilt(struct TreeNode* root) {
    int count = 0;
    treeSum(root, &count);
    return count;
}